1493D - GCD of an Array - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long mod=1e9+7;
struct segmenttree
{
	vector<int> seg;
	void update(int l,int r,int i,int val,int pos)
	{
		if(i<l||r<i) return ;
		if(l==r) { seg[pos]+=val;return ; }
		int mid=(l+r)/2;
		update(l,mid,i,val,pos*2);
		update(mid+1,r,i,val,pos*2+1);
		seg[pos]=min(seg[pos*2],seg[pos*2+1]);
	}
};
segmenttree mp[MAXN];
map<int,int> cnt[MAXN];
int pre[MAXN],pos[MAXN*2],val[MAXN*2],ct[MAXN];
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    for(int i=1;i<MAXN;i++) pre[i]=1e9;
    for(int i=2;i<MAXN;i++) for(int j=i;j<MAXN;j+=i) pre[j]=min(pre[j],i);
    int n,q;
    cin>>n>>q;
    long long ans=1;
    for(int i=1;i<=n+q;i++)
    {
    	if(i<=n)
    	{
    		pos[i]=i;
    		cin>>val[i];
    		int r=val[i];
    		while(r>1) ct[pre[r]]+=(cnt[pre[r]][i]++==0),r/=pre[r];
		}
		else
		{
    		cin>>pos[i]>>val[i];
    		int r=val[i];
    		while(r>1) ct[pre[r]]+=(cnt[pre[r]][pos[i]]++==0),r/=pre[r];
		}
	}
	for(int i=1;i<MAXN;i++) if(ct[i]==n) mp[i].seg.resize(n*4+5);
	for(int i=1;i<=n+q;i++)
	{
		int r=val[i];
    	while(r>1)
    	{
    		if(ct[pre[r]]!=n) { r/=pre[r];continue; }
    		int a=mp[pre[r]].seg[1];
    		mp[pre[r]].update(1,n,pos[i],1,1);
    		if(mp[pre[r]].seg[1]-a) ans=ans*pre[r]%mod;
			r/=pre[r];
		}
		if(i>n) cout<<ans<<"\n";
	}
}